package Leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @ Author     ：侯耀祖
 * @ Description：
 */
public class solveNQueens {

// 存储所有合法的N皇后摆放方案
List<List<String>> result = new ArrayList<>();
// 使用字符数组表示棋盘，'Q'表示皇后，'.'表示空位
char[][] charBoard;

/**
 * 解决N皇后问题，返回所有合法的摆放方案
 * @param n 棋盘的大小，即皇后的数量
 * @return 所有合法的摆放方案
 */
public List<List<String>> solveNQueens(int n) {
    // 初始化棋盘，所有位置默认为空位
    charBoard = new char[n][n];
    for (char[] temp : charBoard){
        Arrays.fill(temp, '.');
    }
    // 从棋盘的第一个位置开始尝试摆放皇后
    backtracking(charBoard, 0, 0);
    return result;
}

/**
 * 回溯法尝试在棋盘上摆放皇后
 * @param charBoard 棋盘
 * @param row 当前尝试摆放的行
 * @param n 棋盘的大小
 */
public void backtracking(char[][] charBoard, int row, int n){
    // 如果已经摆放到了最后一行的下一行，说明已经找到了一个合法方案
    if (row == n){
        // 将当前棋盘的摆放方案添加到结果中
        result.add(ArrayToList(charBoard));
        return;
    }
    // 尝试在当前行的每一列摆放皇后
    for (int i = 0; i < n; i++) {
        // 检查当前位置是否可以摆放皇后
        if (isValid(charBoard, row, i, n)){
            // 摆放皇后
            charBoard[row][i] = 'Q';
            // 继续尝试摆放下一行的皇后
            backtracking(charBoard, row + 1, n);
            // 回溯，撤销当前位置的皇后
            charBoard[row][i] = '.';
        }
    }
}

/**
 * 将字符数组形式的棋盘转换为字符串列表
 * @param charBoard 棋盘
 * @return 字符串列表表示的棋盘
 */
private List<String> ArrayToList(char[][] charBoard) {
    List<String> path = new ArrayList<>();
    StringBuilder builder = new StringBuilder();
    // 遍历每一行的字符，将其拼接成字符串后添加到列表中
    for (char[] chars : charBoard) {
        for (int j = 0; j < charBoard[0].length; j++) {
            builder.append(chars[j]);
        }
        path.add(builder.toString());
        // 清空StringBuilder以用于下一行的拼接
        builder.delete(0, builder.length());
    }
    return path;
}

/**
 * 检查当前位置是否可以摆放皇后
 * @param chessboard 棋盘
 * @param row 当前位置的行
 * @param col 当前位置的列
 * @param n 棋盘的大小
 * @return 如果当前位置可以摆放皇后则返回true，否则返回false
 */
public boolean isValid(char[][] chessboard, int row, int col, int n){
    // 检查当前位置的上方是否有皇后
    for (int j = 0; j < row; j++) {
        if (chessboard[j][col] == ('Q')){
            return false;
        }
    }
    // 检查当前位置的左上方是否有皇后
    for (int j = row - 1, k = col - 1; j >= 0 && k >= 0; j--, k--){
        if (chessboard[j][k] == ('Q')){
            return false;
        }
    }
    // 检查当前位置的右上方是否有皇后
    for (int j = row - 1, k = col + 1; j >= 0 && k < n; j--, k++){
        if (chessboard[j][k] == ('Q')){
            return false;
        }
    }
    // 如果上方、左上方、右上方都没有皇后，则当前位置可以摆放皇后
    return true;
}

}
